package 树.Trie;

public class 实现Trie_前缀树_208 {
    class Trie {
        class TrieNode {
            boolean isWord = false;
            TrieNode[] children;

            public TrieNode() {
                children = new TrieNode[26];//因为本次的输入是26个小写英文字母，所以孩子节点就设置成一个长度为26的数组
            }
        }

        /**
         * Initialize your data structure here.
         */
        TrieNode root;

        public Trie() {
            root = new TrieNode();//构造出来根节点
        }

        /**
         * Inserts a word into the trie.
         */
        public void insert(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该字符在trie中。
                    cur.children[c - 'a'] = new TrieNode();//没有就新建一个
                }

                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            cur.isWord = true; //经过上面的循环整个单词已经插入完成了，所以把isWord置为true
        }

        /**
         * Returns if the word is in the trie.
         */
        public boolean search(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该字符在trie中。
                    return false;//搜索到一个字符没有就直接返回false。比如cat，你都搜索到a没有了，就不用往下搜索了
                }

                //如果有该字符，那么就要走到该节点去。再继续往下搜索
                cur = cur.children[c - 'a'];
            }
            return cur.isWord;//有归有，是不是单词还要看它的isWord属性来判定。
        }

        /**
         * Returns if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            TrieNode cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该字符在trie中。
                    return false;//搜索到一个字符没有就直接返回false。比如cat，你都搜索到a没有了，就不用往下搜索了
                }

                //如果有该字符，那么就要走到该节点去。再继续往下搜索
                cur = cur.children[c - 'a'];
            }
            return true;//全找到的直接返回true
        }
    }

}
